package gold.digger;

import java.util.*;
import java.util.List;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC837 {
    public long startExecuteTime = System.currentTimeMillis();


    /*
     * @param 此题目参考了别人代码
     * 不是因为复杂，而是因为经典
     * 未来需要再次复习此道题目
     * dp反过来复杂度就降低好多啊！
     * @return:
     */
    class Solution {
        public double new21Game(int N, int K, int W) {
            // 先判断 K - 1 + W 是否在 N 的里面，如果在的话，说明肯定能赢得游戏，返回 1.0，也就是 100%
            if (N - K + 1 >= W) {
                return 1.0;
            }
            double[] dp = new double[K + W];
            // 将能赢得游戏的点数的概率设置为 1
            for (int i = K; i <= N; i++) {
                dp[i] = 1.0;
            }
            // 计算K + W 这几个点数的概率和
            double sumProb = N - K + 1;
            // 从 K - 1 开始计算，
            for (int i = K - 1; i >= 0; i--) {
                // 点数为 i 的赢得游戏的概率为 i + 1 ~ i + W 的概率和除以 W
                dp[i] = sumProb / W;
                sumProb = sumProb - dp[i + W] + dp[i];
            }

            return dp[0];
        }
    }


    class Solution_Time_Exceed {
        Map<Integer, Double> memo = new HashMap<>();

        public double new21Game(int n, int k, int maxPts) {
            return dfs(0, n, k, maxPts);
        }

        public double dfs(int curSum, int n, int k, int maxPts) {
            if (curSum >= k) return curSum <= n ? 1 : 0;
            if (memo.containsKey(curSum)) return memo.get(curSum);

            double curPossible = 0;
            for (int i = 1; i <= maxPts; i++) {
                curPossible += dfs(curSum + i, n, k, maxPts) / maxPts;
            }

            memo.put(curSum, curPossible);
            return curPossible;
        }
    }

    public void run() {
        Solution solution = new Solution();

//        输入：N = 10, K = 1, W = 10
//        输出：1.00000
//        说明：爱丽丝得到一张卡，然后停止。
//        System.out.println(solution.new21Game(10, 1, 10));


//        输入：N = 6, K = 1, W = 10
//        输出：0.60000
//        说明：爱丽丝得到一张卡，然后停止。
//        在 W = 10 的 6 种可能下，她的得分不超过 N = 6 分。
//        System.out.println(solution.new21Game(6, 1, 10));

//        输入：N = 21, K = 17, W = 10
//        输出：0.73278
//        System.out.println(solution.new21Game(21, 17, 10));


        System.out.println(solution.new21Game(9676, 8090, 3056));
    }

    public static void main(String[] args) throws Exception {
        LC837 an = new LC837();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
